package leetcode每日一题.leetcode20212;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 1. 问题描述
 *       给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
 *       你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
 *
 * 2. 算法分析
 *      1. 暴力+双指针    代码思路比较简单，但是时间和空间都比较高
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q021_数组的度 {

    /**
     * 暴力+双指针
     * @param nums
     * @return
     */
    public int findShortestSubArray1(int[] nums) {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for(int x : nums) {
            if(!freq.containsKey(x)) {
                freq.put(x,1);
            } else {
                freq.put(x,freq.get(x)+1);
            }
        }
        List<Integer> temp = new ArrayList<>();
        int max = 0;
        for(int key : freq.keySet()) {
            if(freq.get(key) > max) {
                max = freq.get(key);
            }
        }
        for(int key : freq.keySet()) {
            if(freq.get(key) == max) {
                temp.add(key);
            }
        }
        int n = nums.length;
        int min = Integer.MAX_VALUE;
        for(int x : temp) {
            int left = 0;
            int rigth = n - 1;
            while(left < n) {
                if(nums[left] == x) {
                    break;
                }
                left++;
                if(left == n) {
                    break;
                }
            }
            while(rigth >= 0) {
                if(nums[rigth] == x) {
                    break;
                }
                rigth--;
                if(rigth == -1) {
                    break;
                }
            }
            min = Math.min(min,rigth - left + 1);
        }
        return min;
    }


    /**
     * 优化 采用int数组作为hash，相比于HashMap节省了空间，但是时间复杂度上没有太大的提升，还是O(N^2)
     * N为数组中出现频数最多的元素个数
     * @param nums
     * @return
     */
    public int findShortestSubArray2(int[] nums) {
        int[] freq = new int[50000]; // 创建频数数组
        int maxFreq = 0; // 记录数组中的最高频数
        int n = nums.length; // nums数组的个数
        for(int x : nums) {
            freq[x]++;
            if(maxFreq < freq[x]) {
                maxFreq = freq[x];
            }
        }
        int min = Integer.MAX_VALUE; // 记录全局的最小长度
        for(int x : nums) {
            if(freq[x] == maxFreq) {
                int left = 0;
                int rigth = n - 1;
                while(left < n) {
                    if(nums[left] == x) {
                        break;
                    }
                    left++;
                }
                while(rigth >= 0) {
                    if(nums[rigth] == x) {
                        break;
                    }
                    rigth--;
                }
                min = Math.min(min,rigth - left + 1);
            }
        }
        return min;
    }

    /**
     * 优化
     * 优化的思路：不采用for(int x : nums) 而是通过扫描索引的for，这样可以减少当前元素第一次出现的查询
     * 即去掉left的那个while循环，但是此时有一点需要注意，这是在调试的过程中发现的，从具体例子来看：假设
     * 当前数组为[1,2,2,3,3,1,2],第一次扫描到2，求出当前最小为6,这就是我们需要的答案，但是循环并没有结束
     * 如果进行下一次，我们会找到一个更小的为5，但是这并不能包含所有元素，所以之后找到的结果都是不满足的，所以
     * 在代码中添加freq[nums[i]]--;这样就能避免
     * @param nums
     * @return
     */
    public int findShortestSubArray3(int[] nums) {
        int[] freq = new int[50000]; // 创建频数数组
        int maxFreq = 0; // 记录数组中的最高频数
        int n = nums.length; // nums数组的个数
        for(int x : nums) {
            freq[x]++;
            if(maxFreq < freq[x]) {
                maxFreq = freq[x];
            }
        }
        int min = Integer.MAX_VALUE; // 记录全局的最小长度
        for(int i = 0; i < n; i++) {
            if(freq[nums[i]] == maxFreq) {
                int right = n - 1;
                while(right >= 0) {
                    if(nums[right] == nums[i]) {
                        break;
                    }
                    right--;
                }
                min = Math.min(min,right - i + 1);
                freq[nums[i]]--;
            }
        }
        return min;
    }
}
